package org.basis.algorithm.list.practice;

import org.basis.algorithm.list.common.ListNodeUtil;
import org.basis.algorithm.list.common.PairNode;
import org.basis.algorithm.list.common.SingleNode;

import java.util.Stack;

/**
 * 链表反转练习
 *
 * @author Mr_wenpan@163.com 2021/12/13 21:22
 */
public class ListInversion2 {

    public static void main(String[] args) {
        testSingle();


    }

    public static void testSingle() {
        SingleNode<Integer> singleNode = ListNodeUtil.generateIntegerSingleList(20, 30, false);
        ListNodeUtil.printSingleList(singleNode);
        SingleNode<Integer> newHead = reverseSingleListByPoint(singleNode);
        ListNodeUtil.printSingleList(newHead);
        SingleNode<Integer> integerSingleNode = reverseSingleListByStack(newHead);
        ListNodeUtil.printSingleList(integerSingleNode);
    }

    /**
     * 反转单链表: 使用三个指针的方式
     */
    public static SingleNode<Integer> reverseSingleListByPoint(SingleNode<Integer> head) {
        if (head == null || head.next == null) {
            return head;
        }
        SingleNode<Integer> pre = null;
        SingleNode<Integer> cur = head;
        SingleNode<Integer> next = null;
        while (cur != null) {
            next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }

        return pre;
    }

    public static SingleNode<Integer> reverseSingleListByStack(SingleNode<Integer> head) {
        if (head == null || head.next == null) {
            return head;
        }
        Stack<SingleNode<Integer>> stack = new Stack<>();
        SingleNode<Integer> cur = head;

        while (cur != null) {
            // 按顺序压栈
            stack.push(cur);
            cur = cur.next;
        }

        SingleNode<Integer> newHead = stack.pop();
        SingleNode<Integer> current = newHead;

        while (!stack.isEmpty()) {
            SingleNode<Integer> pop = stack.pop();
            current.next = pop;
            current = pop;
        }

        // 最后一个节点（即原来的头节点）手动置为空
//        head.next = null;
        current.next = null;

        return newHead;
    }

    public static PairNode<Integer> reversePairListByPoint(PairNode<Integer> head) {
        if (head == null || head.next == null) {
            return head;
        }
        PairNode<Integer> pre = null;
        PairNode<Integer> cur = head;
        PairNode<Integer> next;

        while (cur != null) {
            // 暂存下一个节点，避免指针反转后找不到下一个节点
            next = cur.next;
            cur.next = pre;
            cur.last = next;
            pre = cur;
            cur = next;
        }

        return pre;
    }

    public static PairNode<Integer> reversePairListByStack(PairNode<Integer> head) {
        if (head == null || head.next == null) {
            return head;
        }
        Stack<PairNode<Integer>> stack = new Stack<>();
        PairNode<Integer> cur = head;
        while (cur != null) {
            stack.push(cur);
            cur = cur.next;
        }

        // 先弹出头元素
        PairNode<Integer> newHead = stack.pop();
        cur = newHead;
        cur.last = null;

        while (!stack.isEmpty()) {
            PairNode<Integer> pop = stack.pop();
            cur.next = pop;
            pop.last = cur;
            // 提前置为空
            pop.next = null;
        }

        return newHead;
    }
}
